public class RedBlackTree {

    public TreeNode root;

    public boolean insert (int val) {
        TreeNode node = new TreeNode(val);
        if(root == null) {
            root = node;
            root.color = Color.BLACK;
            return true;
        }

        //插入结点
        TreeNode parent = null;
        TreeNode cur = root;
        while(cur != null) {
            if(cur.val == val) {
                //相同的数值不能插入
                return false;
            } else if(cur.val > val) {
                parent = cur;
                cur = cur.left;
            } else {
                parent = cur;
                cur = cur.right;
            }
        }

        if(parent.val > val) {
            parent.left = node;
        } else {
            parent.right = node;
        }
        node.parent = parent;

        cur = node;

        while(parent != null && parent.color == Color.RED) {
            TreeNode grandparent = parent.parent; // parent 为红色，一定有父亲结点
            if(parent == grandparent.left) {
                TreeNode uncle = grandparent.right;
                if(uncle != null && uncle.color == Color.RED) {
                    uncle.color = Color.BLACK;
                    parent.color = Color.BLACK;
                    grandparent.color = Color.RED;

                    //继续向上调整颜色
                    cur = grandparent;
                    parent = cur.parent;
                } else {
                    // uncle 结点为空 或者 uncle 结点为黑色结点，最后都需要进行右旋

                    if(cur == parent.right) {
                        //如果 cur 是 parent 的右孩子，则需要先进行左旋
                        rotateLeft(parent);
                        TreeNode tmp = parent;
                        parent = cur;
                        cur = tmp;
                    }

                    //cur 是 parent 的左孩子
                    rotateRight(grandparent);
                    grandparent.color = Color.RED;
                    parent.color = Color.BLACK;

                    //此时红黑树已经调整完成，无需继续向上调整颜色。
                }

            } else {
                //parent == grandparent.right
                TreeNode uncle = grandparent.left;
                if(uncle != null && uncle.color == Color.RED) {
                    uncle.color = Color.BLACK;
                    parent.color = Color.BLACK;
                    grandparent.color = Color.RED;

                    //继续向上调整颜色
                    cur = grandparent;
                    parent = cur.parent;
                } else {
                    // uncle 结点为空 或者 uncle 结点为黑色结点，最后都需要进行左旋

                    if(cur == parent.left) {
                        //如果 cur 是 parent 的左孩子，则需要先进行右旋
                        rotateRight(parent);
                        TreeNode tmp = parent;
                        parent = cur;
                        cur = tmp;
                    }

                    rotateLeft(grandparent);
                    grandparent.color = Color.RED;
                    parent.color = Color.BLACK;

                    //此时红黑树已经调整完成，无需继续向上调整颜色。
                }
            }
        }

        root.color = Color.BLACK;
        return true;
    }

    //左旋
    private void rotateLeft(TreeNode prev) {
        TreeNode cur = prev.right;
        TreeNode curL = cur.left;
        TreeNode parent = prev.parent;

        cur.left = prev;
        prev.parent = cur;
        prev.right = curL;
        if(curL != null) {
            curL.parent = prev;
        }

        if(parent != root) {
            root = cur;
        } else if(parent.left == prev) {
            parent.left = cur;
        } else {
            parent.right = cur;
        }
    }

    //右旋
    private void rotateRight(TreeNode grandparent) {
        TreeNode Pgrandparent = grandparent.parent;
        TreeNode cur = grandparent.left;
        TreeNode curR = cur.right;

        cur.right = grandparent;
        grandparent.parent = cur;
        grandparent.left = curR;
        if(curR != null) {
            curR.parent = grandparent;
        }

        if(Pgrandparent == root) {
            root = cur;
        } else if(Pgrandparent.left == grandparent) {
            Pgrandparent.left = cur;
        } else {
            Pgrandparent.right = cur;
        }
    }

}
